package cn.element.leetcode.random;

/**
 * @description:
 * @author: gonghongwei
 * @create: 2021-06-25 14:50
 */
/*给定一个非负整数c，你要判断是否存在两个整数 a 和 b，使得a2 + b2 = c 。

		示例 1：
		输入：c = 5
		输出：true
		解释：1 * 1 + 2 * 2 = 5

		来源：力扣（LeetCode）
		链接：https://leetcode-cn.com/problems/sum-of-square-numbers
		著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class L633judgeSquareSum {
//	方法一：使用sqrt函数

	public boolean judgeSquareSum(int c) {
		for (long a = 0; a * a <= c; a++) {
			double b = Math.sqrt(c - a * a);
			if (b == (int) b) {
				return true;
			}
		}
		return false;
	}

	//方法二：双指针
	/*本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。

因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。*/
	public boolean judgeSquareSum1(int target) {
		if (target < 0) return false;
		int i = 0, j = (int) Math.sqrt(target);
		while (i <= j) {
			int powSum = i * i + j * j;
			if (powSum == target) {
				return true;
			} else if (powSum > target) {
				j--;
			} else {
				i++;
			}
		}
		return false;
	}

}
